﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Sorts
{
    /// <summary>
    /// 将数组分为两部分：已排序部分和未排序部分，每次遍历找出未排序部分的最小元素，将其交互到已排序部分。
    /// </summary>
    class SelectionSort<T>
        where T : IComparable<T>
    {
        private static void Swap(T[] items, int left, int right)
        {
            if (left != right)
            {
                var temp = items[left];
                items[left] = items[right];
                items[right] = temp;
            }
        }

        public static void Sort(T[] items)
        {
            for (
                var sortedRangeEndIndex = 0;
                sortedRangeEndIndex < items.Length;
                sortedRangeEndIndex++)
            {
                int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEndIndex);
                Swap(items, sortedRangeEndIndex, nextIndex);
            }
        }

        private static int FindIndexOfSmallestFromIndex(T[] items, int sortedRangeEndIndex)
        {
            T currentSmallItem = items[sortedRangeEndIndex];
            int currentSmllIndex = sortedRangeEndIndex;

            for (var i = sortedRangeEndIndex + 1; i < items.Length; i++)
            {
                if (currentSmallItem.CompareTo(items[i]) > 0)
                {
                    currentSmallItem = items[i];
                    currentSmllIndex = i;
                }
            }

            return currentSmllIndex;
        }
    }
}
